public class Solution214 {
    public String shortestPalindrome(String s) {
        int n = s.length();
        if (n < 2) {
            return s;
        }
        char[] p = s.toCharArray();
        int[] next = new int[n];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < n - 1) {
            if (j == -1 || p[i] == p[j]) {
                if (p[++i] == p[++j]) {
                    next[i] = next[j];
                } else {
                    next[i] = j;
                }
            } else {
                j = next[j];
            }
        }
        i = n - 1;
        j = 0;
        while (i >= 0) {
            if (j == -1 || p[i] == p[j]) {
                i--;
                j++;
            } else {
                j = next[j];
            }
        }

        StringBuilder res = new StringBuilder(s.substring(j, n)).reverse().append(p);
        return res.toString();
    }
}
